即興LT: フルスクラッチRustで"世界"の創造主になる
https://scrapbox.io/files/6565cf9fc1d082001cf1ad2d.png
今回のLT
結構ライトです (5分ぐらいで終わる想定)
地形生成について
野望:架空の世界を生成したい
「地図帳の自動生成」
地形、交通網、地名などを自動生成する
最初のステップとして、地形生成に(3年間ぐらい)取り組んできた
そろそろ及第点が見えてきた
先行研究
MinecraftやOpenTTDは地形生成を使ったメディアの代表例
CG的アプローチ
「Generating fantasy maps」by Martin O'Leary
「Polygonal Map Generation for Games」by Amit Patel
地形学的アプローチ
数理モデルに基づいた地形の再現
河川の侵食作用に着目
地形形成の要因のほとんどは、侵食作用に基づいている
各地点に対して、侵食速度と隆起速度が釣り合う標高を反復的に求める
多くは SPIM(Stream Power Incusion Model) に基づいている いろいろある
自分が最も参考にしたもの:
Guillaume Cordonnier, Jean Braun, Marie-Paule Cani, Bedrich Benes, Eric Galin, et al.. Large Scale Terrain Generation from Tectonic Uplift and Fluvial Erosion. Computer Graphics Forum, 2016, Proc. EUROGRAPHICS 2016, 35 (2), pp.165-175. ⟨10.1111/cgf.12820⟩. ⟨hal-01262376⟩
Pythonでは高度なシュミレータが存在
地形をリアルに、高速に生成したい
ここで重要なのは見た目のリアルさで、地形学的に厳密であることは求められない
生成結果は高速に、かつ解析的に求まるものであって欲しい
純粋な地形学的アプローチでは割に合わない
かといって、CG的アプローチではリアルさに欠ける
地形学の要素を取り入れつつ、計算が手元環境で十分に間に合うものを作りたい
今作ってるやつ
"fastlem"
ドキュメント作成中
開発はRustによる
メモリ管理やパフォーマンスを考える手間が省けそう
Web上でも処理できる(wasmビルド対応)
シュミレーションから描画まで、今の所ほとんど自力実装
一部アルゴリズムは既存パッケージに依存
生成の流れ
(1)点群データを生成
空間上にランダムに散りばめる
各点に対して、入力には侵食速度に関するパラメータ(例えば降水量、隆起速度)が、出力では標高が紐付けられる
(2) 河川を作成し、各点を結ぶ
隣り合っている点に対して、最も標高の下向き傾斜が大きい点に線を結び続ける
(3) 各点に対して流域面積を求め、入力パラメータに基づいて侵食速度を求める
(4) 侵食速度を標高へフィードバック
(5) (2)へ戻り、処理を繰り返す
標高が安定したら生成を終了
技術的側面
アルゴリズムの実装が多い
特に、空間情報の処理
ドロネー三角形分割 (ドロネー図の作成)
地形のデータは、空間上に散らばった点データ上でシュミレーション・マッピングされる
河川をシュミレーション・表現するには、点データ同士の繋がりをグラフで表現する必要がある
いい感じのグラフを作成するのに使うのがドロネー三角形分割
各地点の流域面積がSPIMパラメータの一つとなるが、それを求めるにはボロノイ図が必要
ドロネー図とボロノイ図は双対(どちらかがわかればどちらかが作れる)
補間
点データの存在しない場所のデータの値(標高など)を、周辺の点データから求めたい
キュービックスプラインなど1Dのものはよく知られているが、2Dになると実装が途端に難しくなる
Natural Neighbor Interpolation
点群中のデータを「自然に」補間する
描画時に使う
空間インデックス
空間データをいい感じに取り出す
R-treeなど
補間の高速化に使用 (与えられた点がどのドロネー三角形に重なっているかを調べる)
パーリンノイズ等のノイズジェネレーターも必要
入力パラメータを生成するため
乱数だと不都合なので、なめらかなノイズが必要
Procedural Generationは (自分の今までやってきた範囲だと) 空間情報のアルゴリズムのオンパレード
交通網生成にもなると、A*のような探索アルゴリズムや、L-systemも出てくる
たのしい(にっこり)